1. Field of the Invention
The present invention relates to a system and a method for modeling acoustic reverberation at interactive rates, using pre-computed data structures to accelerate beam tracing and propagation path generation.
2. Description of Prior Art
Computer-aided acoustic modeling is an important tool for designing and simulating three-dimensional (3D) environments. For example, an architect may evaluate the acoustic properties of a proposed building design, or a factory designer may predict the sound levels of any machine at any position on a factory floor, using acoustic models.
Acoustic modeling can also be used to provide a more realistic immersive virtual environment. For example, modeled acoustics may be used to provide sound cues to assist a user""s navigation through, and communication in, immersive virtual environments. More specifically, the voices of users sharing a virtual environment may be spatialized according to the each user""s avatar location. For 3D video games, sounds may be spatialized to help a player navigate and localize competing participants.
The primary challenge in spatializing sound in such environments is computing the significant number of viable propagation paths from a sound source position to a listener""s receiving location. Because sound generally travels between a source and a receiver along a large number of paths, via reflection, transmission, and diffraction, accurate acoustic simulation is extremely computationally expensive. To illustrate this point, consider the example of FIG. 1 which shows a simple two-room environment, and just some of the possible propagation paths from a sound source S to a receiver R located in an adjacent room.
Prior acoustic modeling approaches can generally be classified into four types: image source methods; radiant exchange methods; ray tracing methods; and beam tracing. Beam tracing is the basis for the approach set forth in this application.
Beam tracing methods classify reflection paths originating from a source position by recursively tracing pyramidal beams (i.e., a set of rays) through space. More specifically, a set of pyramidal beams is constructed that completely covers the two-dimensional (2D) space of directions from the source. For each beam, polygons are considered for intersection in front-to-back order from the source. As intersecting polygons are detected, the original beam is xe2x80x9cclippedxe2x80x9d to remove the shadow region created by the intersecting polygon, a transmission beam is constructed matching the shadow region, and a reflection beam is constructed by mirroring the transmission beam over the intersecting polygon""s plane. For example, as illustrated in FIG. 2, a reflection beam Ra is constructed by mirroring a transmission beam over surface a, using Sxe2x80x2 as a virtual beam source. Transmission beam Ta is constructed matching the shadow region created by surface a.
A significant advantage of beam tracing over the image source method is that fewer virtual sources need be considered for environments with arbitrary geometry. Since each beam represents the region of space for which a corresponding virtual source (at the apex of the beam) is visible, high-order virtual sources must be considered only for reflections off polygons intersecting the beam. For instance, referring to FIG. 3, consider the virtual source Sa which results from the reflection of the beam originating from S over polygon a. The corresponding reflection beam, Ra, intersects exactly the set of polygons (c and d) for which second-order reflections are possible after specular reflection off polygon a. Other polygons (b, e, f, and g) need not be considered for second-order reflections after a, thus significantly pruning the recursion tree of virtual sources.
A significant disadvantage of conventional beam tracing techniques, however, is that the geometric operations which are required to trace a beam through a 3D environment (i.e., computing intersections, clipping, and mirroring) are computationally expensive. Because each beam may be reflected and/or obstructed by several surfaces, particularly in complex environments, it is difficult to perform the necessary geometric operations on beams efficiently, as they are recursively traced through the spatial environment. For acoustic modeling to be effective in immersive virtual environments, computations must be completed at interactive rates so that spatialized audio output can be updated as the user navigates through the environment.
Much prior work in virtual environment systems has focused on visualization (i.e., methods for rendering more realistic images or for increasing image refresh rates). For example, Heckbert and Hanrahan, xe2x80x9cBeam Tracing Polygonal Objects,xe2x80x9d Computer Graphics (SIGGRAPH ""84), 18, 3, 119-127 describe a graphics illumination technique in which pyramidal beams, represented by their 2D polygonal cross-sections, are traced recursively from a viewpoint to a point light source using a pre-computed xe2x80x9clight beam treexe2x80x9d data structure. Teller, xe2x80x9cVisibility Computations in Densely Occluded Polyhedral Environments,xe2x80x9d Ph.D. thesis, Computer Science Division (EECS), University of California, Berkeley, 1992, describes a beam tracing algorithm for computing a xe2x80x9cpotentially visible setxe2x80x9d of polygons to render from a particular viewpoint in a computer graphics scene using cell adjacency and xe2x80x9cstab treexe2x80x9d data structures.
On the other hand, relatively little attention has been directed to auralization (i.e., rendering realistic spatialized sound using acoustical modeling). Yet, improved acoustic modeling can help provide users with a completely immersive virtual experience, in which aural and visual cues are combined to support a more natural interaction in a virtual environment. Due to the computational complexity discussed above, however, prior acoustic modeling techniques, such as conventional beam tracing, have been unable to realize accurate acoustic auralization in complex environments at interactive rates. Furthermore, such techniques have essentially disregarded complex scattering phenomena, such as diffraction and diffuse reflection.
The acoustic modeling technique according to the present invention efficiently utilizes a combination of pre-computed data structures to accelerate evaluation of acoustic propagation paths so that sound can be modeled and auralized in real-time, even in complex environments. According to the present invention, an input spatial model is initially partitioned into convex polyhedra (cells). Pairs of neighboring cells which share a polygonal boundary(s) are linked to form a cell adjacency graph. For each sound source, convex pyramidal beams are traced through the spatial model via depth-first recursive traversal of the cell adjacency graph. At each cell boundary, the beam is split and trimmed into possibly several convex beams representing paths of transmission, specular reflection, diffuse reflection, and diffraction.
During depth-first traversal of the cell adjacency graph, a beam tree data structure is generated to represent the regions of space reached by each potential sequence of transmission, specular reflection, diffuse reflection, and diffraction events at cell boundaries. This beam tree data structure enables fast computation of propagation paths to an arbitrary receiver position. Using the beam tree data structure to trace paths from a source to a receiver, acceptable computation rates for updating an acoustic model can be achieved so as to be suitable for interactive environments.